package com.fengye.algorithms.leecode.dp;

/**
 * @author loupf50246
 * @date 2023/7/7 19:32
 */
public class StockMaxProfitIII123 {

    public static void main(String[] args) {
        int[] prices = {3,3,5,0,0,3,1,4};
        maxProfit2(prices);
    }

    public static int maxProfit2(int[] prices) {
        int[][] dp = new int[3][prices.length];
        for (int i=1;i<=2;i++) {
            int max = Integer.MIN_VALUE >> 1;
            for (int j=1; j<prices.length;j++) {
                // 记录前j-1天，买一次的最大利润
                max = Math.max(max, dp[i-1][j-1] - prices[j-1]);
                // dp[i][j-1] 表示第j天没有任何操作的最大利润
                // prices[j]+max表示第j天卖出一支股票的最大利润
                dp[i][j] = Math.max(dp[i][j-1], prices[j] + max);
            }
        }
        return dp[2][prices.length-1];
    }

    public static int maxProfit1(int[] prices) {
        // 表在第j天结束之后最多交易i次所能获得的最大利润
        int[][] dp = new int[3][prices.length];
        for (int i=1; i<=2;i++) {
            for (int j=1;j<prices.length;j++) {
                // k表示交易的次数，0表示没有交易，不用计算
                for (int k=j-1;k>=0;k--) {
                    int max = 0;
                    if (k == 0) {
                        // k等于0表示在第一天买入，在第j天卖出，这种情况下
                        // 最多交易一次，不需要dp[i-1][j-1]
                        max = Math.max(dp[i][j-1], prices[j] - prices[k]);
                    } else {
                        // 递推公式
                        // 要么第j天不进行任何操作，要么第j天卖出，
                        // 如果卖出需要找到卖出的最大利润
                        // 这里k不一定是买入股票最低的那天，需要包含前面交易的利润
                        // 所以是prices[j] - prices[k] + dp[i-1][k-1]
                        max = Math.max(dp[i][j-1], prices[j] - prices[k] + dp[i-1][k-1]);
                    }
                    dp[i][j] = Math.max(dp[i][j], max);
                }
            }
        }
        return dp[2][prices.length-1];
    }
}
